A priority encoder is a digital circuit which selects one of several input bits to remain asserted at a set of corresponding outputs, with all other output bits remaining deasserted. In the prior art, the logic decision as to which bit should remain asserted is typically based on a predefined, fixed priority or precedence of the bit positions.
For instance, in a four bit fixed priority encoder having input bits IN(3), IN(2), IN(1) and IN(0), the circuit could be constructed so that the most significant input bit IN(3) has the highest priority, followed by bit IN(2), followed by bit IN(1), and ending with bit IN(0) having the lowest priority. If, for example, an input vector has bit IN(3) deasserted and bits IN(2), IN(1) and IN(0) asserted (i.e., an input of 0111), this priority encoder will produce an output bit vector 0100. Even though input bit IN(3) has the highest priority, its corresponding output OUT(3) is deasserted since it was deasserted at the input. Output OUT(2) is asserted, however, since it corresponds to the input having the highest priority of all asserted input bits. Also, in this example, outputs OUT(1) and OUT(0) are deasserted, since they are associated with a lower priority input than the highest priority asserted input.
Priority encoders are used in a number of critical applications such as instruction queue structures within high performance data processors. This type of priority encoder provides fast arbitration between events occurring in the queue. For example, the queue typically holds multiple pending instructions which require access to a given processor resource. Therefore, only one instruction can be granted access to the resource at a time as selected by a priority encoder. Priority encoders are also used in datapath structures where the characteristics of the data itself are used to control datapath flow, such as in normalization circuits used in a floating point processor.
Traditional queue structures such as those used in data processors are organized with a fixed priority, with one queue entry pre-allocated in hardware to have the highest priority, an adjacent entry the next highest priority, and so on. As such, these encoders always use the same precedence.
In the prior art, there are two circuit configurations typically used to build fixed priority encoders. FIG. 1 illustrates a first type of fixed priority encoder 100 which employs a carry chain circuit 101. Input bit IN(3).sub.-- L is the highest priority input, followed by IN(2).sub.-- L, IN(1).sub.-- L, and then IN(0).sub.-- L . In this circuit, the input signal sense is inverted; that is, a low voltage input signal indicates an asserted or logic true input, as indicated by the notation ".sub.-- L".
In operation, the carry chain 101 is pre-charged during a low phase of a clock signal (CLK) 102 by pre-charge transistors 103a through 103e. This places nodes ZZ(3) through ZZ(0) into an initial high state. After input vector reception, the clock signal (CLK) 102 enters the high state which turns off pre-charge transistors 103a through 103e, and turns on transistor 104, which creates a conductive path from node VGND 107 to a reference ground voltage. This inserts a zero bit into one end of the chain (i.e., grounding one end) to define the bit position of highest priority. Then, based on the input vector applied to inputs IN(0).sub.-- L through IN(3).sub.-- L, any deasserted inputs (which will be in a high state) activate transistors 105d through 105a. The first asserted input (in a low state) which occurs to the right of node VGND 107 will stop the propagation of the VGND 107 signal (since that input's transistor 105 will not activate), causing the corresponding output to enter a high state, with all other following outputs remaining in a low state. The location where the zero bit stops propagating (i.e. the last ZZ(N) location grounded) identifies the highest priority input bit that was asserted, as indicated by a high state only at that input's corresponding output.
A second type of fixed priority encoder circuit 130 is shown in FIG. 2 having input IN(3) assigned the highest priority. Note that in this circuit the input signal logic sense is normal such that an asserted or logic true input is represented by a high voltage state or a "1".
The fixed priority encoder 130 includes a grid of wires defined by row wires I(0) through I(3) and column wires J(0) through J(3). A KILLED(I).sub.-- L wire also extends along each row wire I. If an input in a higher priority position is asserted, this input turns on a pull-down transistor connected to all lower priority KILLED(I).sub.-- L wires, thus grounding out these lines and their outputs to a deasserted state. For an output bit OUT(I) to be asserted, therefore, the corresponding input IN(I) must have been asserted, and the KILLED(I).sub.-- L wire coupled to that input IN(I) must also not have been pulled down by another higher priority input.
In operation, when clock signal (CLK) 120 is low, kill wires KILLED(3).sub.-- L through KILLED(0).sub.-- L are initialized to a high state via pullup transistors 121a through 121d which couple each kill wire to a reference voltage, Vdd. When the clock signal (CLK) 120 enters the high state with the input vector already received, the input bits IN(0) through IN(3) are logically ANDed via respective AND gates 122a through 122d, causing only the asserted input bits to be passed through to the row or "input-to-output" wires I(0) through I(3). Note that for each input-to-output wire I(0) through I(3), there is a connection to a corresponding column or input-to-kill wire J(0) through J(3). When any input-to-output wire I(N) is in a high state, the input-to-kill wire J(N) to which it is connected is, therefore, also in a high state. The connections between the input-to-output wires I (N) and the input-to-kill wires J (N) are located along the diagonal starting at the upper left corner of the grid.
Also coupled to each input-to-kill wire J(N) are respective transistors 123 through 128. Each transistor 123 through 128 is able to ground out a corresponding KILLED(I).sub.-- L wire to place an associated output OUT(I) in a deasserted state, as controlled by the corresponding input-to-kill wire J(I) from an input IN having a higher priority.
Essentially, upon assertion of a higher priority input, all KILLED(I).sub.-- L wires associated with any lower priority inputs IN are brought to a low state. At each output OUT(0) through OUT(3), each KILLED(N).sub.-- L wire is ANDed with the state of the input-to-output wire by AND gates 129a through 129d. As such, any asserted inputs IN(3) through IN(0) always have their respective outputs deasserted via a KILLED(N).sub.-- L wire which is set low by any higher priority input that was asserted.
In the fixed priority encoder in FIG. 2, in order to change the priority from the existing configuration, the grid locations of transistors 123 through 128 must change for the desired precedence. In other words, a whole new circuit must be created. FIGS. 3a through 3d illustrate four such precedence configurations or circuits.
The precedence of each priority encoder in FIGS. 3a through 3d is determined by where the transistors (unnumbered) are connected between the I(J) wires and KILLED(I).sub.-- L wires in the transistor grid array. FIG. 3a shows the transistor connections, as in FIG. 2, for a highest to lowest precedence IN(3), IN(2), IN(1) and IN(0). FIG. 3b shows the transistor connections required when the priority of inputs is IN(2), IN(1), IN(0) and IN(3), respectively. Similarly, FIG. 3c shows a precedence of IN(1), IN(0), IN(3), and IN(2), respectively and FIG. 3d shows a precedence of IN(0), IN(3), IN(2), IN(1).